package Algorithm.DynamicPlanning;

public class Code09_PalindromeSubsequence {

    public static int maxLen1(String str){
        if (str == null || str.length() == 0){
            return 0;
        }
        char[] str1 = str.toCharArray();
        char[] str2 = reverse(str1);
        return lcse(str1, str2);
    }

    public static char[] reverse(char[] str){
        char[] reverse = new char[str.length];
        for (int i = str.length - 1; i >= 0; i--) {
            reverse[str.length - i - 1] = str[i];
        }
        return reverse;
    }

    public static int lcse(char[] str1, char[] str2){
        int n = str1.length;
        int[][] dp = new int[n][n];
        dp[0][0] = str1[0] == str2[0] ? 1 : 0;
        // 填充边界
        for (int j = 1; j < n; j++){
            dp[0][j] = Math.max(dp[0][j - 1], (str1[0] == str2[j] ? 1 : 0));
        }
        for (int i = 1; i < n; i++){
            dp[i][0] = Math.max(dp[i - 1][0], (str1[i] == str2[0] ? 1 : 0));
        }
        // 普遍情况
        for (int i = 1; i < n; i++) {
            for (int j = 1; j < n; j++){
                dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                if (str1[i] == str2[j]){
                    dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - 1] + 1);
                }
            }
        }
        return dp[n - 1][n - 1];
    }

    public static void main(String[] args) {
        String test = "A1BC2D33FG2H1I";
        System.out.println(maxLen1(test));
        //System.out.println(maxLen2(test));
    }
}
